Error control needs to be exercised on the communication process to ensure correct data transmission in a communication system. CRC is characterized by simple coding and low misjudging rate and is an error control mode commonly used in the communication system.
CRC codes are a branch of linear block codes, and the basic principle is as follows: With a line ar coding theory being used, an r-bit check code (namely, a CRC code) is generated according to a k-bit information sequence to be transmitted on the transmitting end and by using a certain rule, the CRC code is appended to the original information bits to make up a new sequence composed of (k+r) bits, and the new sequence that includes the CRC code is sent; on the receiving end, it is checked, according to the rule between the information bits and the CRC code, whether an error occurs in the transmission process.
For example, if a k-bit binary information sequence composed of information bits to be transmitted is D={d[p−1]d[p−2] . . . d[1]d[0]}, the CRC works in this way: Sequence D is shifted leftward by r bits, the shifted sequence D is divided by a generator polynomial composed of (r+1) bits to obtain an r-bit remainder function R={r[r−1]r[r−2] . . . r[1]r[0]}, the remainder function R is used as a CRC code of the sequence D, and a new binary sequence M={d[p−1]d[p−2] . . . d[1]d[0]r[r−1]r[r−2] . . . r[1]r[0]} composed of (k+r) bits is generated for transmission.
In actual application, CRC codes can be implemented by logic circuits of hardware. Typically, there are two kinds of the logic circuits: a serial circuit and a parallel circuit. The serial circuit calculates a CRC code bit by bit. For example, as shown in FIG. 1(a), for a 4-bit CRC code (CRC-4), the four registers are reset to 0, and then information elements in an information sequence are used as input data, and the information elements are input serially in a shift mode, namely, one information bit element is input in every clock cycle. After four clock cycles, the first four information bits of the information element are all input into the registers. Subsequently, data in the registers move leftward bit by bit, and an XOR operation is performed for the data in the registers and a CRC code is calculated. Supposing that a generator polynomial of CRC-4 is x4+x+1, FIG. 1(b) shows a serial circuit without waiting for shifting the information elements into the register before calculating the CRC code.
The implementation of a parallel circuit is based on the preceding serial circuit. The principle of the parallel circuit is as follows: The CRC remainder generated at the time of inputting n information bits into the parallel circuit simultaneously is the same as the CRC remainder generated at the time of inputting n information bits into the serial circuit bit by bit; therefore, the parallel circuit may be regarded as equivalent to the serial circuit, and a logical relation expression of the parallel circuit can be obtained according to the registers in the serial circuit and changes of the input information bits. Through the parallel circuit, n information bits to be transmitted can be input at a time. After n information bits are input repeatedly, the CRC code of the information sequence may be finally obtained. FIG. 2 shows a general parallel circuit.
In the process of implementing the present invention, the inventor finds at least the following problems in the prior art:
Based on a line feedback shift register in the prior art, the serial circuit can shift only one bit in each clock cycle, which is rather inefficient; such serial circuits can be applicable to only low-rate CRC check circuit that imposes a low requirement on performance, and cannot be applicable to the CRC that requires high rates to perform data check.
In the prior art, when a parallel circuit processes multiple bits in parallel, with the increase of the bit width of parallel data, deeper layers of the XOR logic circuit are used by the parallel circuit. Consequently, the corresponding circuit delay is greater, and the clock frequency of the circuit is lower. The operation performance or data throughput of a circuit is in direct proportion to the clock frequency of the circuit and the bit width of data. The prior art decreases the clock frequency of the circuit when increasing the bit width of data being processed, and is incapable of improving the circuit performance or increasing the data throughput linearly by increasing the bit width of parallel data linearly. Furthermore, the parallel circuit in the prior art is incapable of processing high-rate CRC data.